package com.cb2.algorithm.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/find-bottom-left-tree-value/">找树左下角的值(Find Bottom Left Tree Value)</a>
 * <p>给定一个二叉树的 根节点 root，请找出该二叉树的 <b>最底层</b> <b>最左边</b> 节点的值。</p>假设二叉树中至少有一个节点。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: root = [2,1,3]
 *              2
 *             / \
 *            1   3
 *      输出: 1
 *
 * 示例 2:
 *      输入: [1,2,3,4,null,5,6,null,null,7]
 *                  1
 *                 / \
 *                2   3
 *               /   / \
 *              4   5   6
 *                 /
 *                7
 *      输出: 7
 * </pre>
 * </p>
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>二叉树的节点个数的范围是 [1,10^4]</li>
 *     <li>-2^31 <= Node.val <= 2^31 - 1 </li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/8 17:24
 */
public class LC0513FindBottomLeftValue_M {
    static class Solution {
        public int findBottomLeftValue(TreeNode root) {
            //return findBottomLeftValueByIteration(root);
            return findBottomLeftValueByRecursion(root);
        }

        private int findBottomLeftValueByIteration(TreeNode root) {
            if (root == null) {
                throw new IllegalArgumentException();
            }
            Queue<TreeNode> helper = new LinkedList<>();
            helper.offer(root);
            int result = -1;
            while (!helper.isEmpty()) {
                int currLevelNodeSize = helper.size();
                for (int i = 0; i < currLevelNodeSize; i++) {
                    TreeNode currNode = helper.poll();
                    if (i == 0) {
                        result = currNode.val;
                    }
                    if (currNode.left != null) {
                        helper.offer(currNode.left);
                    }
                    if (currNode.right != null) {
                        helper.offer(currNode.right);
                    }
                }
            }
            return result;
        }

        int maxLevel = 0;
        int nodeVal = -1;

        private int findBottomLeftValueByRecursion(TreeNode root) {
            findBottomLeftValueByRecursion(root, 1);
            return nodeVal;
        }

        private void findBottomLeftValueByRecursion(TreeNode root, int currLevel) {
            if (root == null) {
                return;
            }
            if (currLevel > maxLevel) {
                maxLevel = currLevel;
                nodeVal = root.val;
            }
            findBottomLeftValueByRecursion(root.left, currLevel + 1);
            findBottomLeftValueByRecursion(root.right, currLevel + 1);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(6);
        root.right.left.left = new TreeNode(7);
        Solution solution = new Solution();
        System.out.println(solution.findBottomLeftValue(root));
    }
}
